<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width,initial-scale=1.0">
    <title>线性表详情</title>
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/semantic-ui@2.4.2/dist/semantic.min.css">
    <link rel="stylesheet" href="../static/css/typo.css">
    <link rel="stylesheet" href="../static/lib/prism/prism.css">
    <link rel="stylesheet" href="../static/lib/tocbot/tocbot.css">
    <link rel="stylesheet" href="../static/css/me.css">
    <style>
        p{
            text-indent: 2em !important;
        }
    </style>
</head>
<body>
<!--导航-->
<nav class="ui inverted attached segment m-padded-tb-mini m-shadow-small">
    <div class="ui container">
      <!--为了适应手机端查看页面，添加stackable属性，代表可堆叠，给grid之前加上stackable-->
      <div class="ui inverted secondary stackable menu">
        <h2 class="ui teal header item">数据结构</h2>
          <a href="#" class="active m-item item m-mobile-hide"><i class="mini file icon"></i>线性表</a>
          <a href="#" class="m-item item m-mobile-hide"><i class="mini file icon"></i>哈希表</a>
          <a href="#" class="m-item item m-mobile-hide"><i class="mini file icon"></i>树</a>
          <a href="#" class="m-item item m-mobile-hide"><i class="mini file icon"></i>图</a>
          <a href="#" class="m-item item m-mobile-hide"><i class="mini file icon"></i>算法</a>
          <div class="right m-item item m-mobile-hide">
              <!-- transparent搜索框显示为透明 inverted颜色反转 -->
              <div class="ui icon inverted transparent input">
                  <input type="text" placeholder="Search....">
                  <i class="search link icon"></i>
              </div>
          </div>
    </div>
    </div>
    <!--点击再显示，加一个图标  menu toggle只是为了使用，另一种方法也可以用id  -->
    <a href="#" class="ui menu toggle black icon button m-right-top m-mobile-show">
        <i class="sidebar icon"></i>
    </a>
</nav>

<!--中间内容-->

<div  class="m-container-small m-padded-tb-big">
  <div class="ui container">
      <div class="ui top attached segment">
          <!--头部-->
        <div class="ui  horizontal link list">

        </div>
      </div>
      <div class="ui  attached segment">
          <!--图片区域-->
          <img src="../static/images/list.jfif" alt="" class="ui fluid rounded image">
      </div>
      <div class="ui attached padded segment">
          <!--内容部分-->
          <div class="ui right aligned basic segment">
            <div class="ui blue basic label">线性表</div>
          </div>
          <h2 class="ui center aligned header">线性表</h2>
          <br>
          <div id="content" class="typo typo-selection js-toc-content  m-padded-lr-responsive m-padded-tb-large">
            <h2 id="section1">一、基本概念 </h2>
            <p><b>线性表</b> 是最基本、最简单、最常用的一种数据结构，还可细分为顺序表、链表、栈和队列。</p>
            <h4>1.线性表的特征</h4>
              <ul>
                  <li>集合中必存在唯一的一个“第一元素”。</li>
                  <li>集合中必存在唯一的一个 “最后元素” 。</li>
                  <li>除最后一个元素之外，均有唯一的后继(后件)。</li>
                  <li>除第一个元素之外，均有唯一的前驱(前件)。</li>
              </ul>
            <h4>2.线性表的存储结构</h4>
              <p>线性表主要由顺序表示或链式表示。在实际应用中，常以栈、 队列、 字符串等特殊形式使用。</p>
              <p><b>顺序</b> 表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像 （sequential
                  mapping）。它以“物理位置相邻”来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。</p>
              <p><b>链式</b> 表示指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。它的存储单元可以是连续的，也可
                  以是不连续的。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息 （即直接
                  后继的存储位置），这两部分信息组成数据元素的存储映像，称为结点 （node）。它包括两个域；存储数据元素信息的域称为数
                  据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。</p>
             <h2 id="section2">二、线性表的存储</h2>
            <h4>1.顺序存储结构</h4>
              <p>用一组地址连续的存储单元依次存储线性表的数据元素。顺序表对数据的物理存储结构也有要求。顺序表存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依次存储起来，存储时做到数据元素之间不留一丝缝隙。
                  顺序表的优缺点：逻辑上相邻的两个元素在物理上也相邻；他的存储位置可以通过公式直接计算；需要预分配较大空间；做插入、删除操作时要移动大量元素；表的容量难以扩充。
              </p>
              <pre class="language-css"><code class="language-css">
                  <p>// --- 线性表的动态分配顺序存储结构 ---
                #define LIST_INIT_SIZE 100
                // 线性表存储空间的初始分配量
                #define LISTINCREMENT  10
                // 线性表存储空间的分配增量
                typedef struct{
                    ElemType *elem;
                // 存储空间基址
                    int      length;
                // 当前长度
                    int      listsize;
                // 当前分配的存储容量（以 sizeof(ElemType)为单位）
                }SqList;</p></code></pre>
            <h4>2.链式存储结构</h4>
              <p>可以用一组任意的存储单元存储线性表的数据元素。链表，别名链式存储结构或单链表，用于存储逻辑关系为 "一对一" 的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。
                  链表每个数据元素在存储时都配备一个指针，用于指向自己的直接后继元素。<b>结点</b> 是数据元素的存储映像，它包括数据域和指针域。
                  <b>数据域</b>中存储数据元素信息。<b>指针域</b> 中存储直接后继存储位置，这一位置信息被称为指针或链。</p>
              <h4>3.单链表、循环链表和双向链表</h4>
              <p><b>单链表:</b>  其每个结点中只包含一个直接指向后继指针域。</p>
              <p><b>循环链表：</b>  整个链表的指针域链接成环。</p>
              <p><b>双向链表：</b>  每一个结点包含两个指针域，其一指向直接后继，另一指向直接前驱。</p>
              <p><b>双向循环链表：</b> 将头结点和尾结点链接起来的双向链表。</p>
              <p><b>静态链表：</b> 借用一维数组来描述线性链表。</p>
              <pre class="language-css"><code class="language-css">
              // --- 线性表的单链表存储结构 ---
                  typedef struct LNode{
                  ElemType     data;
                  struct LNode *next;
                  }LNode, LinkList;

            // --- 线性表的双向链表存储结构 ---
            typedef struct DuLNode{
                ElemType       data;
                struct DuLNode *prior, *next;
            }DuLNode, DuLinkList;

            // --- 线性表的静态单链表存储结构 ---
            # define MAXSIZE 100
            typedef struct{
                ElemType data;
                int      cur;
            }component, SLinkList[MAXSIZE];</code></pre>
<h2 id="section3">三、线性表的主要操作算法设计与实现：</h2>
    <h4>1.初始化线性表</h4>
    <pre class="language-css"><code class="language-css">
    Status InitList_Sq(SqList *L){
    // 创造一个空的线性表L
    L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (! L->elem) exit(OVERFLOW);  // 存储分配失败
    L->length = 0;                  // 空表长度为0
    L->listsize = LIST_INIT_SIZE;   // 初始存储容量
    return OK;
}</code></pre>
    <h4>2.创建单链表</h4>
    <pre class="language-css"><code class="language-css">
    LinkList *CreateList_L(int n){
        // 逆序输入 n 个元素的值，建立带表头结点的单链表 L
        LinkList *L, *p; int i;
        L = (LinkList *)malloc(sizeof(LNode));
        L->next = NULL;                 // 先建立一个带头结点的单链表
        for(i=n; i>0; --i){
            p = (LNode *)malloc(sizeof(LNode));  // 生成新结点
            p->data = random(200);               // 填入随机数
            p->next = L->next; L->next = p;      // 插入到表头
        }
        return L;
    }</code></pre>
     <h4>3.双向循环链表插入元素</h4>
    <pre class="language-css"><code class="language-css">
    Status ListInsert_DuL(DuLinkList *L, int i, ElemType e){
    DuLinkList *p, *q;  int j;
    if(i<1) return ERROR;
    p = L;  j = 0;
    while(p->next!=L && j<i-1){  // 在 L 中确定插入位置
        p = p->next;  j++;
    }
    if(p->next!=L || (p->next==head&&j==i-1)){
        q = (DuLinkList*)malloc(sizeof(DuLinkList));
        q->data = e;
        q->next = p->next;  q->prior = p;
        p->next->prior = q;  p->next = q;
        return OK;
    }
    else return ERROR;
}</code></pre>

<h2 id="section4">三、栈和队列</h2>
  <h4>1.栈的基本概念</h4>
    <p>线性表主要由顺序表示或链式表示。在实际应用中，常以 栈、 队列、 字符串等特殊形式使用。</p>
  <p><b>栈</b> 是限制在线性表的一端进行插入和删除操作的线性表，也称为后进先出（Last In First Out, LIFO）线性表。
  栈顶（top）允许进行插入、删除操作的一段，也称为表尾。栈底（bottom）固定端，也称为表头。<b>空栈</b> 表中没有元素。</p>
  <h5>栈的存储</h5>
  <pre class="language-css"><code class="language-css">
    // --- 栈的动态分配顺序存储结构 ---
    #define STACK_INIT_SIZE 100   // 存储空间初始分配量
    #define STACKINCREMENT  10    // 存储空间分配增量
    typedef struct {
        SElemType  *base;   // 在栈构造之前和销毁之后，base 的值为 NULL
        SElemType  *top;    // 栈顶指针
        int  stacksize;     // 当前已分配的存储空间，以元素为单位
    }DySqStack;
    // --- 栈的静态分配顺序存储结构 ---
    # define MAX_STACK_SIZE 100
    typedef struct{
        SElemType stack_array[MAX_STACK_SIZE];
        int top;
    }StSqStack;
  // --- 栈的链式存储结构 ---
  typedef struct Node{
    SElemType data;
    struct Node *next;
}LinkedStack;</code></pre>
  <h4>2.队列的基本概念</h4>
  <p><b>队列</b> 队列是一种线性数据结构；日常生活中的排队是一种典型的队列，不允许插队；一端插入，另一端删除，先进先出。满足数据元素先进先出或者后进后出的操作的一种特殊的线性表。允许插入的一端称为队尾(rear) ，允许删除的一端称为队头(front)。<b>循环队列</b>将为队列分配的向量空间看作一个首尾相接的圆环。</p>
  <h5>队列的存储</h5>
  <pre class="language-css"><code class="language-css">
  // --- 队列的存储结构 ---
  #define MAXQSIZE 100
  typedef struct{
    QElemType queue_array[MAX_QSIZE];  // 最大存储空间
    int       front;  // 头指针，若队列不空，指向队列头元素
    int       rear;   // 尾指针，若队列不空，指向队列尾元素的下一个位置
  }SqQueue;
  // --- 队列的链式存储结构 ---
  typedef struct Node{
    SElemType data;
    struct Node *next;
}LinkedStack;</code></pre>

</body>
</html>